package BinarySearch;

import java.util.Arrays;

public class _475_Heaters {
    public int findRadius(int[] houses, int[] heaters) {
        int radius = Integer.MIN_VALUE;
        Arrays.sort(heaters);
        for (int house : houses) {
            int start = 0;
            int end = heaters.length - 1;
            while (start + 1 < end) {
                int middle = (start + end + 1) / 2;
                if (heaters[middle] < house) {
                    start = middle;
                } else if (heaters[middle] > house) {
                    end = middle;
                } else {
                    start = middle;
                    break;
                }
            }
            if (heaters[start] == house || heaters[end] == house) {
                radius = Math.max(0, radius);
                continue;
            }
            int temp = Math.min(Math.abs(heaters[start]- house), Math.abs(heaters[end] - house));
            radius = Math.max(radius, temp);
        }
        return radius;
    }
}
